//斐波那契数列递归改进-》记忆化
public class code4 {
    static int cnt = 0;//记录递归了多少次
    static int[] data = new int[25];//存储斐波那契数

    public static void main(String[] args) {
        System.out.println(fib(20));
        System.out.println(cnt);
    }

    public static int fib(int n) {
        cnt++;
        if (data[n]!=0) return data[n];//记忆化搜索：已经算过了
        //递归出口
        if(n==1||n==2) {
            data[n] = 1;
            return data[n];
        }
        data[n] = fib(n-1) + fib(n-2);
        return data[n];
    }
}
